二叉搜索树

• 也叫 二叉排序树：左子树节点都比当前节点小，右子树都比当前节点大。（类似数组中的 二分查找法）

构建二叉搜索树

const arr = [];
for (let i = 0; i < 10000; i ++) {
    arr[i] = Math.floor(Math.random() * 10000);
}

function Node (value) {
    this.value = value;
    this.left = null;
    this.right = null;
}

// 构建节点
function addNode (root, num) {
    if (root == null) return;
    if (root.value == num) return;
    if (root.value < num) {
        if (root.right == null) root.right = new Node(num);  // 右节点为空，则创建节点
        else addNode(root.right, num);  // 不为空，向下递归
    } else {
        if (root.left == null) root.left = new Node(num);
        else addNode(root.left, num);
    }
}

// 构建二叉树
function buildSearchTree (arr) {
    if (arr == null || arr.length == 0) return null;
    var root = new Node(arr[0]);
    for (let i = 0; i < arr.length; i ++) {
        addNode(root, arr[i]);
    }
    return root;
}

const tree = buildSearchTree(arr);
console.log(tree);

搜索 二叉搜索树

function serachByTree (root, target) {
    if (root == null) return false;
    if (root.value == target) return true;
    if (root.value > target) return serachByTree(root.left, target);  // 向左节点进行递归搜索
    else return serachByTree(root.right, target);  // 向右节点进行递归搜索
}

serachByTree(tree, 9612);  //-->